package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 * 题解：https://leetcode.cn/problems/rotate-array/solutions/551039/xuan-zhuan-shu-zu-by-leetcode-solution-nipk
 *
 * @author yulongTian
 * @create 2024-05-28 11:32
 */
public class Test15 {
    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22};
        int[] nums = {1};
        int k = 1;
        new Test15().rotate(nums, k);
        System.out.println(Arrays.toString(nums));
    }

    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    /**
     * 数组翻转
     *
     * @param nums
     * @param start
     * @param end
     */
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }

//    /**
//     * 尝试 O(1) 的空间复杂度
//     * 37/38
//     * 第37个用例错误
//     *
//     * @param nums
//     * @param k
//     */
//    public void rotate(int[] nums, int k) {
//        int len = nums.length;
//        k %= len;
//        if (k == 0) {
//            return;
//        }
//        if (len == 2) {
//            if (k == 0) {
//                return;
//            } else {
//                int temp = nums[0];
//                nums[0] = nums[1];
//                nums[1] = temp;
//                return;
//            }
//        }
//        // 判断k和len的最大公因数是否为1，是则false
//        int[] temp = check(len, k);
//        if (temp[0] != 1) {
//            rotateDetail(nums, k, true, temp[1]);
//            return;
//        }
//        rotateDetail(nums, k, false, 0);
//
//    }
//
//    private int[] check(int a, int b) {
//        if (a > b) {
//            int c = a;
//            a = b;
//            b = c;
//        }
//        int p = a, c = b;
//        while (b % a != 0) {
//            int l = a;
//            a = b % a;
//            b = l;
//        }
//        return new int[]{a, p * c / a};//最大公因数
//    }
//
//    private void rotateDetail(int[] nums, int k, boolean flag, int c) {
//        int len = nums.length;
//        int i = 0;
//        int source = 0;
//        int target = k % len;
//        int tempSource = nums[source];
//        int tempTarget = nums[target];
//        while (i < len) {
//            nums[target] = tempSource;
//            tempSource = tempTarget;
//
//            if (flag && (i + 1) % (c / k) == 0 && i != 0) {
//                target = (target + 1) % len;
//                tempSource = nums[(target - k + len) % len];
//            } else {
//                target = (target + k) % len;
//            }
//            tempTarget = nums[target];
//            i++;
//        }
//    }

//    /**
//     * O(n) 空间复杂度
//     *
//     * @param nums
//     * @param k
//     */
//    public void rotate(int[] nums, int k) {
//        k %= nums.length;
//        if (k == 0) {
//            return;
//        }
//        int[] twoNums = new int[nums.length * 2];
//        for (int i = 0; i < nums.length; i++) {
//            twoNums[i] = nums[i];
//        }
//        for (int i = 0; i < nums.length; i++) {
//            twoNums[i + nums.length] = nums[i];
//        }
//        for (int i = 0; i < nums.length; i++) {
//            nums[i] = twoNums[i + nums.length - k];
//        }
//    }

}
